package caculate.sliding_window;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-04-08 20:13
 **/
public class MinWindow {

    public static void main(String[] args) {
        String s = "ADOBECODEBANCA";
        String t = "ABC";
        System.out.println(minWindow(s, t));
        System.out.println(minWindow_1(s, t));
    }

    public static String minWindow(String s, String t) {
        int left = 0, right = 0, minLeft = 0, minRight = Integer.MAX_VALUE;

        int sLen = s.length();

        int[] cntS = new int[128];
        int[] cntT = new int[128];

        for (char c : t.toCharArray()) {
            cntT[c]++;
        }

        while (right < sLen) {
            char c = s.charAt(right);
            cntS[c]++;
            while (isConvert(cntS, cntT)) {
                if (right - left < minRight - minLeft) {
                    minLeft = left;
                    minRight = right;
                }
                cntS[s.charAt(left)]--;
                left++;
            }

            right++;
        }

        return left == 0 ? "" : s.substring(minLeft, minRight + 1);
    }

    public static String minWindow_1(String s, String t) {
        int left = 0, right = 0, minLeft = 0, minRight = Integer.MAX_VALUE;

        int sLen = s.length();

        // 记录t字符串的总字符数
        int less = t.length();
        int[] cnt = new int[128];

        for (char c : t.toCharArray()) {
            cnt[c]++;
        }

        while (right < sLen) {
            char c = s.charAt(right);
            cnt[c]--;
            // 该字符出现次数刚好抵消
            if (cnt[c] >= 0) {
                less--;
            }

            while (less == 0) {
                if (right - left < minRight - minLeft) {
                    minLeft = left;
                    minRight = right;
                }

                char x = s.charAt(left);
                if (cnt[x] == 0) {
                    less++;
                }
                cnt[x]++;
                left++;
            }

            right++;
        }

        return left == 0 ? "" : s.substring(minLeft, minRight + 1);
    }

    public static boolean isConvert(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }

        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }

        return true;
    }

}
